iT邦幫忙

2021 iThome 鐵人賽

DAY 17
0

今日題目

題目連結:700. Search in a Binary Search Tree
題目主題:Tree, Binary Search Tree, Binary Tree


簡單說說 Binary Search Tree

昨天分享了 Binary Search Tree 的原則,今天來説說Binary Search Tree 是怎麼快速找到目標值的。

Binary Search Tree 的原則是越左邊的值越小、越右邊的值越大,也就是説根節點的左半部一定都小於根節點、右半部一定都大於根節點,如果要搜尋一個值,會從根節點開始走,運作過程如下圖:

範例: tree = [5, 2, 6, 1, 3, null, 8]

目標值:8
https://ithelp.ithome.com.tw/upload/images/20211001/20141336xzfyuiDGVp.png

目標值大於根節點,直接往右走,走到第二層是 6 ,目標值 8 還是大於 6 ,所以繼續往右走,最終搜尋到這棵樹裡面有 8。

目標值:3
https://ithelp.ithome.com.tw/upload/images/20211001/20141336rvsxtUdW3v.png

目標值小於根節點,直接往左走,走到第二層是 2 ,目標值 3 大於 2 ,所以接著往右走,最終搜尋到這棵樹裡面有 3。

目標值:10
https://ithelp.ithome.com.tw/upload/images/20211001/20141336WFXE46IwJ1.png

目標值大於根節點,直接往右走,走到第二層 6 ,目標值 10 還是大於 6 ,所以繼續往右走,第三層是 8 發現 10 還是比較大,所以又往下一層右邊走,但發現已經沒有節點了,所以可以下結論這棵樹裡面沒有 10 這個值。


題目解說

建議可以看看LeetCode原本的題目說明,這邊是用我的方式說明題目,參考就好。

題目會給一個Binary Search Tree及一個目標值,目標是確認這個目標值是否在這顆Binary Search Tree中,若有出現的話,回傳目標值所在的TreeNode,若沒找到回傳 Null 代表沒有。

約束:

  • 這是一顆Binary Search Tree
  • 樹的節點總數範圍在[1, 5000]
  • 1 <= Node.val <= 10的7次方
  • 1 <= val <= 10的7次方

範例1
https://ithelp.ithome.com.tw/upload/images/20211001/20141336hDex5muyQw.png

輸入:root = [4,2,7,1,3], val = 2
輸出:[2, 1, 3]
解說:目標值 2 在 root 裡面有出現,因此回傳 2 這個TreeNode,參考上圖。

範例2

輸入:root = [4,2,7,1,3], val = 5
輸出:[]
解說:目標值 5 在 root 裡面找不到,因此回傳null

建議到這邊先停下來,嘗試自己解解看,若沒有想法可再繼續走下去。


解題的想像

文字描述

  1. 寫一個遞迴方法,每次使用傳進一個TreeNode及目標值。
  2. 每次進入方法會檢查以下:
    • 目前是否有節點,若沒有節點代表這棵樹不存在目標值,回傳 Null 結束。
    • 目前節點的值是否與目標值相同,若相同回傳目前節點結束。
    • 目標值若小於目前節點的值,往目前節點的左邊子節點走。
    • 目標值若大於目前節點的值,往目前節點的右邊子節點走。

圖解過程

範例:root = [5, 2, 6, 1, 3, null, 8]
目標值:3

https://ithelp.ithome.com.tw/upload/images/20211001/20141336RhaoIWx03N.png

如上圖所示,目標值為 3 小於根節點的值 5 先往左走,走到第二層目標值 3 大於目前節點的值 2 ,所以接著往右走,最終搜尋到這棵樹裡面有 3 這個節點,最終回傳這個節點結束。

若因為沒想法而走到這邊,建議看完想像以後再給自己一次機會試一次。


程式碼撰寫

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # 若沒有節點,代表走到樹的底且目標值不在樹中
        if root == None: return None
        # 若有與目標值相同值的節點,代表找到目標回傳這個節點
        if root.val == val: return root
        
        # 若值大於目前節點的值,往下層右邊節點走
        if val > root.val:
            return self.searchBST(root.right, val)
        # 若值小於目前節點的值,往下層左邊節點走
        if val < root.val:
            return self.searchBST(root.left, val)

希望您今天能瞭解到...

  1. Binary Search Tree 搜尋值
  2. 700. Search in a Binary Search Tree 的解題方法

若內容有什麼問題或建議歡迎一起交流:)
感謝您今天願意花時間看完這篇文章~~~~

Next:501. Find Mode in Binary Search Tree


上一篇
Day 16:108. Convert Sorted Array to Binary Search Tree
下一篇
Day 18:501. Find Mode in Binary Search Tree
系列文
我在刷LeetCode時邂逅了Python30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言